package me.project.offer;

/**
 * 请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。
 * 路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。
 * 如果一条路径经过了矩阵中的某一个格子，则之后不能再次进入这个格子。
 *
 * 例如 a b c e s f c s a d e e 这样的3 X 4 矩阵中包含一条字符串"bcced"的路径，
 * 但是矩阵中不包含"abcb"路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，
 * 路径不能再次进入该格子。
 * <br/>
 * Note:
 *      回溯法，用递归实现
 * @author Mcdull
 * @date 2018-7-4
 */
public class Solution12 {
    //表示上下左右四个方向
    private final static int[][] next = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};
    private int rows;
    private int cols;

    public boolean hasPath(char[] array, int rows, int cols, char[] str) {
        if (array == null || rows == 0 || cols == 0) {
            return false;
        }
        this.cols = cols;
        this.rows = rows;
        //标记矩阵
        boolean[][] marked = new boolean[rows][cols];
        char[][] matrix = builtMatrix(array, rows, cols);
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (backTracking(matrix, str, marked, 0, i, j)) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean backTracking(char[][] matrix, char[] str,
                                 boolean[][] marked, int pathLen, int r, int c) {
        //全部匹配
        if (pathLen == str.length){
            return true;
        }
        //当前位置不匹配 或 已经标记过
        if (r < 0 || r >= rows || c < 0 || c >= cols || matrix[r][c] != str[pathLen] || marked[r][c]){
            return false;
        }
        marked[r][c] = true;
        //分上下左右四个位置递归求解
        for (int[] aNext : next) {
            //有越界的风险
            if (backTracking(matrix, str, marked, pathLen + 1, r + aNext[0], c + aNext[1])) {
                return true;
            }
        }
        //当前递归的路线求解失败，要把这条线路上的标记清除掉
        //因为其他起点的路径依旧可以访问本路径上的节点。
        marked[r][c] = false;
        return false;
    }

    private char[][] builtMatrix(char[] array, int rows, int cols) {
        char[][] matrix = new char[rows][cols];
        for (int i = 0, idx = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                matrix[i][j] = array[idx++];
            }
        }
        return matrix;
    }


    public static void main(String[] args) {
        Solution12 s = new Solution12();
        char[] chars = {'1', '2', '3', '4', '5', '6', '7', '8', '9'};
        char[][] m = s.builtMatrix(chars, 3, 3);
        s.printMatrix(m);

    }

    private void printMatrix(char[][] c) {
        for (char[] aC : c) {
            for (char anAC : aC) {
                System.out.print(String.valueOf(anAC) + " ");
            }
            System.out.println("");
        }
    }
}
